package Offer54;

import java.util.*;

/**
 * @author 23737
 * @time 2021.9.17
 * 二叉搜索树的第K大结点值:
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 */
public class Test {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(4);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        System.out.println(new Solution().kthLargest(treeNode1, 2));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/*自己的解法，时空复杂度比较高
思路：使用BFS将树节点的值存入一个集合中，然后使用集合进行排序，最后得到某个节点的值就行*/
class Solution {
    public int kthLargest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<TreeNode> arrayList = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            arrayList.add(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        Collections.sort(arrayList, new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return o1.val - o2.val;
            }
        });
        return arrayList.get(arrayList.size() - k).val;
    }
}

/*大佬解法：使用中序遍历加提前返回*/
class SolutionTwo {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}


class SolutioThreen {
    public int kthLargest(TreeNode root, int k) {
        /**
         * 思路，利用右中左的遍历顺序，既是从大到小的遍历，
         * 定义一个res 值，记录循环次数
         * 利用栈，先将右边的所有元素压栈，弹栈的同时调整k的大小，当k==0时返回弹出的元素
         */
        if (root == null || k < 1) {
            return -1;
        }

        final Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode res = null;
        TreeNode p = root;

        while (!stack.isEmpty() && k > 0){
            //将树的所有右节点压入栈中
            if (p != null && p.right != null) {
                p = p.right;
                stack.push(p);
                //当树的全部右子树压入栈后，开始弹出，弹出的第一个就是最大值
            } else {

                p = stack.pop();
                res = p;
                //每弹出一个就k-1
                k--;
                if (p.left != null) {
                    p = p.left;
                    stack.push(p);
                } else {
                    p = null;
                }
            }
        }
        //表示因为stack弹出来所有的数据，也没有找到目标数据
        if (k > 0) {
            return -1;
        }
        return res.val;
    }
}


